'''
Created on 2010-2-16

@author: summit
'''

import sys
from Exception import *

class LinkedList(object):
    '''
    Linked list class. Singly-linked list has four myriad implementation variations
    
    '''
    class Element(object):
        '''
        An element of a linked list.
        '''
        
        def __init__(self, list, datum, next):
            '''
            (LinkedList.Element, LinkedList, Object, LinkedList.Element) -> None
            Constructs a list element with the given values.
            '''
            self._list = list
            self._datum = datum
            self._next = next
        
        def getDatum(self):
            return self._datum
        
        datum = property(fget=lambda self: self.getDatum())
        
        def getNext(self):
            return self._next
        
        next = property(fget=lambda self: self.getNext())
        
        def insertAfter(self, item):
            self._next = LinkedList.Element(self._list, item, self._next)
            if self._list._tail is self:
                self._list.tail = self._next
        
        def insertBefor(self, item):
            tmp = LinkedList.Element(self._list, item, self)
            if self is self._list._head:
                self._list._head = tmp
            else:
                prevPtr = self._list._head
                while prevPtr is not None and prevPtr._next is not self:
                    prevPtr = prevPtr._next
                prevPtr._next = tmp
        
        def extract(self):
            prevPtr = None
            if self._list._head is self:
                self._list._head = next
            else:
                prevPtr = list._head
                while prevPtr is not None and prevPtr._next is not self:
                    prevPtr = prevPtr._next
                if prevPtr is None:
                    raise InternalError
                prevPtr._next = next
            if self._list._tail is self:
                self._list._tail = prevPtr

    def __init__(self):
        '''
        Constructor
        '''
        self._head = None
        self._tail = None
    
    def purge(self):
        self._head = None
        self._tail = None
        
    def getHead(self):
        return self._head
    
    head = property(fget=lambda self: self.getHead())
    
    def getTail(self):
        return self._tail
    
    tail = property(fget=lambda self: self.getTail())
    
    def getIsEmpty(self):    
        return self._head is None
    
    isEmpty = property(fget=lambda self: self.getIsEmpty())
    
    def getFirst(self):
        if self._head is None:
            raise ContainerEmpty
        return self._head
    
    first = property(fget=lambda self: self.getFirst())
    
    def getLast(self):
        if self._tail is None:
            raise ContainerEmpty
        return self._tail
    
    last = property(fget=lambda self: self.getLast())
    
    def prepend(self, item):
        tmp = self.Element(self, item, self._head)
        if self._head is None:
            self._tail = tmp
        self._head = tmp
    
    def append(self, item):
        tmp = self.Element(self, item, None)
        if self._head is None:
            self._head = tmp
        else:
            self._tail._next = tmp
        self._tail = tmp
    
    def __copy__(self):
        '''
         Returns a shallow copy of this linked list.
        '''
        result = LinkedList()
        ptr = list._head
        while ptr is not None:
            result.append(ptr._datum)
            ptr = ptr._next
        return result
    
    def extract(self, item):
        '''
        Extracts the given item from this list.
        '''
        ptr = self._head
        prevPtr = None
        while ptr is not None and ptr._datum is not item:
            prevPtr = ptr
            ptr = ptr._next
        if ptr is None:
            raise KeyError
        if ptr == self._head:
            self._head = ptr._next
        else:
            prevPtr._next = ptr._next
        if ptr == self._tail:
            self._tail = prevPtr
    
    def __str__(self):
        string = "LinkedList {"
        ptr = self._head
        while ptr is not None:
            string = string + str(ptr._datum)
            if ptr._next is not None:
                string = string + ", "
            ptr = ptr._next
        string = string + "}"
        return string
    
    def main(*argv):
        "LinkedList test propram."
        print LinkedList.main.__doc__
        ll = LinkedList()
        ll.append(57)
        ll.append("hello")
        ll.append(None)
        tmp = ll.getFirst()
        ll.prepend(tmp.datum)
        print ll
        print "is Empty returns %s" % (ll.isEmpty)
        return 0
    main = staticmethod(main)
    
if __name__ == "__main__":
    sys.exit(LinkedList.main(*sys.argv))